Corelab Seminar
2018-2019
Grigorios Koumoutsos
Competitive Algorithms for Generalized k-Server
Abstract.
The k-server problem is one of the most natural and fundamental online problems and its study has been quite influential in the development of competitive analysis. Despite various remarkable developments, several natural variants and generalizations of the k-server problem are very poorly understood. In particular, they exhibit very different and intriguing behavior and the techniques for the standard k-server problem do not apply to them. Getting a better understanding of such problems is a natural step towards building a deeper theory of online computation.
In this talk, I will discuss some recent results on generalizations of the k-server problem, in particular:
i) the weighted k-server problem, in which servers have different weights;
ii) the generalized k-server problem, where each server lies in its own metric space; and (if time allows)
iii) the resource augmentation version (the (h,k)-server problem), where the performance of the online algorithm with k servers is compared to the offline optimal solution with h ≤ k servers.
SHORT BIO: Grigorios Koumoutsos is a postdoctoral researcher in the Algorithms Research group at Université Libre de Bruxelles (ULB), http://homepages.ulb.ac.be/~gkoumout , hosted by John Iacono. He obtained his PhD in 2018 from TU Eindhoven under the supervision of Nikhil Bansal. He did his undergraduate studies in University of Athens, Dept. of Informatics and Telecommunications and obtained his MSc from University Paris Diderot.